from itertools import product
from random import choice, random, seed

from pygame import Surface
from pygame.display import flip
from pygame.draw import line, rect
from pygame.time import delay

from ..pylib.game import getWindow, waiting, waitQuit

arrwall = [[[' │', '─┛'], ['│┃', '┓┫']], [['─┗', '━┻'], ['┏┣', '┳╋']]]
# "╳"
dpos = ((0, 1), (1, 0), (0, -1), (-1, 0))


class Cell:
    def __init__(self, defaultWall: bool = True):
        self.tag: dict = {}
        self.wall: dict[tuple[int], bool] = {
            (0, 1): defaultWall,
            (1, 0): defaultWall,
            (0, -1): defaultWall,
            (-1, 0): defaultWall,
        }

    def __getitem__(self, index):
        return self.tag.get(index, None)

    def __setitem__(self, index, value):
        self.tag[index] = value


class Maze:
    def __init__(self, size: tuple, lencell: int = 10):
        self.size = self.width, self.height = size
        self.board: dict[tuple, Cell] = {}
        self.lencell = lencell
        for i in range(self.width):
            for j in range(self.height):
                self.board[i, j] = Cell()
        self.reseTag()

    def __getitem__(self, index):
        return self.board.get(index, Cell())

    def __setitem__(self, index, value):
        self.board[index] = value

    def __repr__(self):
        return f"Maze(size={self.size})"

    def __str__(self):
        ret = ''
        for j in range(2 * self.height + 1):
            for i in range(2 * self.width + 1):
                x, y = i // 2, j // 2
                wall = [
                    self.hasWall((x, y - 1), (x, y)),
                    self.hasWall((x - 1, y), (x, y)),
                    self.hasWall(((i - 1) // 2, y - 1), ((i - 1) // 2, y)),
                    self.hasWall((x - 1, (j - 1) // 2), (x, (j - 1) // 2)),
                ]
                if j % 2:
                    wall[0] = wall[2] = 0
                if i % 2:
                    wall[1] = wall[3] = 0
                ret += arrwall[wall[0]][wall[1]][wall[2]][wall[3]]
            ret += '\n' if j < 2 * self.height else ''
        return ret

    def reseTag(self) -> None:
        board = self.board
        for i, j in product(range(self.width), range(self.height)):
            board[i, j].tag = {
                'x': i,
                'y': j,
            }

    def corner(self, x: int, y: int) -> "tuple[int]":
        corner = {
            (0, 0): (0, 0),
            (1, 0): (self.width - 1, 0),
            (0, 1): (0, self.height - 1),
            (1, 1): (self.width - 1, self.height - 1),
        }
        return corner.get((x, y), (None, None))

    def per(self, x: float, y: int) -> "tuple[int]":
        return int(x * (self.width - 1)), int(y * (self.height - 1))

    def breakWall(self, fr: tuple, to: tuple) -> None:
        """打破从fr到to的墙"""
        dx, dy = to[0] - fr[0], to[1] - fr[1]
        f = self.board.get(fr, None)
        t = self.board.get(to, None)
        if f is not None and t is not None:
            f.wall[dx, dy] = False
            t.wall[-dx, -dy] = False

    def ruin(self, chance=0.6) -> "Maze":
        for i in range(self.width - 1):
            for j in range(self.height):
                if random() < chance:
                    self.breakWall((i, j), (i + 1, j))
        for j in range(self.height - 1):
            for i in range(self.width):
                if random() < chance:
                    self.breakWall((i, j), (i, j + 1))
        return self

    def hasWall(self, fr: tuple, to: tuple) -> bool:
        dx, dy = to[0] - fr[0], to[1] - fr[1]
        f = self.board.get(fr, Cell(defaultWall=False))
        t = self.board.get(to, Cell(defaultWall=False))
        return f.wall[dx, dy] or t.wall[-dx, -dy]

    def neighbor(self, pos: "tuple[int]") -> "set[tuple[int]]":
        """返回一个单元的所有邻居的集合"""
        ret = set()
        x, y = pos
        for dx, dy in dpos:
            x1, y1 = x + dx, y + dy
            if self.exist(x1, y1):
                ret.add((x1, y1))
        return ret

    def reachable(self, pos: "tuple[int]") -> "set[tuple[int]]":
        ret = set()
        x, y = pos
        for dx, dy in dpos:
            x1, y1 = x + dx, y + dy
            if self.exist(x1, y1) and not self.hasWall((x, y), (x1, y1)):
                ret.add((x1, y1))
        return ret

    def exist(self, x: int, y: int) -> bool:
        return 0 <= x < self.width and 0 <= y < self.height

    def makeMaze(self, sed: int = None) -> "Maze":
        for _ in makeMaze_iter(self, sed):
            pass
        self.reseTag()
        return self

    def standboard(self) -> Surface:
        sur = Surface(
            (self.width * self.lencell, self.height * self.lencell)
        ).convert_alpha()
        sur.fill((0,) * 4)
        return sur

    def drawall(self, sur: Surface, col=(0, 0, 0, 255)) -> None:
        le, l = self.lencell, self.lencell / 2
        for i in range(self.width):
            for j in range(self.height):
                cell = self.board[i, j]
                x, y = i * le, j * le
                for dx, dy in dpos:
                    if cell.wall[dx, dy]:
                        lx, ly = (dx + 1) * l, (dy + 1) * l
                        line(sur, col, (x + lx, y), (x + lx, y + le)) if dx else 0
                        line(sur, col, (x, y + ly), (x + le, y + ly)) if dy else 0

    def drawbg(self, sur: Surface, style: "dict[str,tuple]") -> None:
        le = self.lencell
        for i in range(self.width):
            for j in range(self.height):
                cell = self.board[i, j]
                for tag in style:
                    if cell[tag]:
                        rect(sur, style[tag], (i * le, j * le, le, le))
                        break

    def draw(self, sur: Surface, style: "dict[str,tuple]") -> None:
        sur.fill((255,) * 3)
        self.drawbg(sur, style)
        self.drawall(sur)
        flip()

    def toimg(self, style: "dict[str,tuple]") -> None:
        window = getWindow(
            (self.width * self.lencell, self.height * self.lencell), repr(self)
        )
        self.draw(window, style)
        waiting()

    def BFS(self, fr, to) -> "list[tuple[int]] | None":
        visiting = [fr]
        visited = set(visiting)
        while visiting:
            tovisit = visiting.pop(0)
            if tovisit == to:
                return self._extracted_from_AStar_7(to, tovisit, fr)
            for pos in self.reachable(tovisit) - visited:
                visiting.append(pos)
                visited.add(pos)
                self[pos]["before"] = tovisit

    def DFS(self, fr, to) -> "list[tuple[int]] | None":
        visiting = [fr]
        visited = set(visiting)
        while visiting:
            tovisit = visiting.pop(-1)
            if tovisit == to:
                return self._extracted_from_AStar_7(to, tovisit, fr)
            for pos in self.reachable(tovisit) - visited:
                self._extracted_from_AStar_13(tovisit, pos, visiting, visited)

    def AStar(self, fr, to) -> "list[tuple[int]] | None":
        self[fr]["F"] = distINF(fr, to)
        visiting = [fr]
        visited = set(visiting)
        while visiting:
            index, minF = 0, self[visiting[0]]['F']
            for i, pos in enumerate(visiting):
                if self[pos]['F'] < minF:
                    index = i
                    minF = self[visiting[i]]['F']
            tovisit = visiting.pop(index)
            if tovisit == to:
                return self._extracted_from_AStar_7(to, tovisit, fr)
            for pos in self.reachable(tovisit) - visited:
                self[pos]['F'] = distINF(fr, pos) + distINF(pos, to)
                self._extracted_from_AStar_13(tovisit, pos, visiting, visited)

    # TODO Rename this here and in `BFS`, `DFS` and `AStar`
    def _extracted_from_AStar_13(self, tovisit, pos, visiting, visited):
        self[pos]["before"] = tovisit
        visiting.append(pos)
        visited.add(pos)

    # TODO Rename this here and in `BFS`, `DFS` and `AStar`
    def _extracted_from_AStar_7(self, to, tovisit, fr):
        way = [to]
        while tovisit != fr:
            tovisit = self[tovisit]["before"]
            way.insert(0, tovisit)
        return way


def distINF(fr: "tuple[int]", to: "tuple[int]") -> int:
    return abs(fr[0] - to[0]) + abs(fr[1] - to[1])


def dist2(fr: "tuple[int]", to: "tuple[int]") -> int:
    dx, dy = fr[0] - to[0], fr[1] - to[1]
    return (dx * dx + dy * dy) ** 0.5


def makeMaze_iter(self: Maze, sed: int = None, fr: tuple = (-1, 0)):
    if sed:
        seed(sed)
    visiting = fr
    unvisited = set(self.board) - {
        visiting,
    }
    visited = [visiting]
    while unvisited:
        if nei := self.neighbor(visiting) & unvisited:
            next_ = choice(list(nei))
            self.breakWall(visiting, next_)
            unvisited.remove(next_)
            visited.append(next_)
            self[visiting]["visiting"] = False
            self[next_]["visiting"] = True
            self[next_]["visited"] = True
            visiting = next_
        else:
            self[visiting]["visiting"] = False
            self[visiting]["abandon"] = True
            visiting = visited.pop()
            self[visiting]["visiting"] = True
            self[visiting]["abandon"] = True
        yield visiting
    while visited:
        self[visiting]["visiting"] = False
        self[visiting]["abandon"] = True
        visiting = visited.pop()
        self[visiting]["visiting"] = True
        self[visiting]["abandon"] = True
        yield visiting


def AStar_iter(self: Maze, fr: tuple, to: tuple, heurist=distINF):
    self[fr]['G'] = 0
    self[fr]['H'] = heurist(fr, to)
    visiting = {fr}
    dead = set()
    self[fr]["keypoint"] = True
    self[to]["keypoint"] = True
    while visiting:
        tovisit = min(visiting, key=lambda pos: self[pos]['G'] + self[pos]['H'])
        visiting.remove(tovisit)
        self[tovisit]["visiting"] = True
        self[tovisit]["todo"] = False
        if tovisit == to:
            while tovisit != fr:
                self[tovisit]["way"] = True
                self[tovisit]["visiting"] = False
                tovisit = self[tovisit]["before"]
                self[tovisit]["visiting"] = True
                yield tovisit
            break
        for pos in self.reachable(tovisit):
            G = self[tovisit]['G'] + 1
            cell = self[pos]
            if (
                cell["todo"]
                and G < cell['G']
                or not cell["todo"]
                and cell["visited"]
                and G < cell['G']
            ):
                cell['G'] = G
                cell["before"] = tovisit
                if cell["visited"]:
                    dead.remove(pos)
                    cell["visited"] = False
                    visiting.add(pos)
                    cell["todo"] = True
            elif not cell["todo"] and not cell["visited"]:
                cell['G'] = G
                cell['H'] = heurist(pos, to)
                visiting.add(pos)
                cell["todo"] = True
                cell["before"] = tovisit
        yield tovisit
        self[tovisit]["visiting"] = False
        dead.add(tovisit)
        self[tovisit]["visited"] = True


def BestFS_iter(self: Maze, fr: tuple, to: tuple, heurist=distINF):
    self[fr]['H'] = heurist(fr, to)
    visiting = {fr}
    visited = {fr}
    self[fr]["keypoint"] = True
    self[to]["keypoint"] = True
    while visiting:
        tovisit = min(visiting, key=lambda pos: self[pos]['H'])
        visiting.remove(tovisit)
        self[tovisit]["visiting"] = True
        self[tovisit]["todo"] = False
        if tovisit == to:
            while tovisit != fr:
                self[tovisit]["way"] = True
                self[tovisit]["visiting"] = False
                tovisit = self[tovisit]["before"]
                self[tovisit]["visiting"] = True
                yield tovisit
            break
        for pos in self.reachable(tovisit) - visited:
            visiting.add(pos)
            visited.add(pos)
            self[pos]['H'] = heurist(pos, to)
            self[pos]["todo"] = True
            self[pos]["before"] = tovisit
        yield tovisit
        self[tovisit]["visiting"] = False
        self[tovisit]["visited"] = True


def BFS_iter(self: Maze, fr: tuple, to: tuple):
    visiting = [fr]
    visited = {fr}
    self[fr]["keypoint"] = True
    self[to]["keypoint"] = True
    while visiting:
        tovisit = visiting.pop(0)
        self[tovisit]["visiting"] = True
        self[tovisit]["todo"] = False
        yield tovisit
        if tovisit == to:
            while tovisit != fr:
                self[tovisit]["way"] = True
                self[tovisit]["visiting"] = False
                tovisit = self[tovisit]["before"]
                self[tovisit]["visiting"] = True
                yield tovisit
            break
        for pos in self.reachable(tovisit) - visited:
            visiting.append(pos)
            visited.add(pos)
            self[pos]["todo"] = True
            self[pos]["before"] = tovisit
        self[tovisit]["visiting"] = False
        self[tovisit]["visited"] = True


def DFS_iter(self: Maze, fr: tuple, to: tuple):
    visiting = [fr]
    visited = set(visiting)
    self[fr]["keypoint"] = True
    self[to]["keypoint"] = True
    while visiting:
        tovisit = visiting.pop(-1)
        self[tovisit]["visiting"] = True
        self[tovisit]["todo"] = False
        yield tovisit
        if tovisit == to:
            while tovisit != fr:
                self[tovisit]["way"] = True
                self[tovisit]["visiting"] = False
                tovisit = self[tovisit]["before"]
                self[tovisit]["visiting"] = True
                yield tovisit
            break
        for pos in self.reachable(tovisit) - visited:
            visiting.append(pos)
            visited.add(pos)
            self[pos]["todo"] = True
            self[pos]["before"] = tovisit
        self[tovisit]["visiting"] = False
        self[tovisit]["visited"] = True


def showMaking(self: Maze, ite, style: dict, dely=0, step=1):
    window = getWindow(
        (self.width * self.lencell, self.height * self.lencell), repr(self)
    )
    ite = enumerate(ite)
    for i, _ in ite:
        if waitQuit():
            for _ in ite:
                ...
            self.reseTag()
            return
        if not i % step:
            self.draw(window, style)
            if dely:
                delay(dely)
    self.draw(window, style)
    waiting()
    self.reseTag()
